package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * 两个链表求交点:
 * 先求长度法
 * hash表法
 * 交替遍历法
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC160 implements LinkedProblem {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //boundary check
        if (headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        //if a & b have different len, then we will stop the loop after second iteration
        while (a != b) {
            //for the end of first iteration, we just reset the pointer to the head of another linkedlist
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }

        return a;
    }
}
